from collections import deque


def numIsland(grid):
    if grid == None or len(grid) == None:
        return 0
    res = 0
    row = len(grid)
    col = len(grid[0])
    q = deque()  # [[1,2],[2,3]]
    for i in range(row):
        for j in range(col):
            if grid[i][j] == '1':
                res += 1
                q.append([i, j])
                grid[i][j] = '0'
                while len(q) > 0:
                    cur = q.pop()
                    x = cur[0]
                    y = cur[1]
                    if x - 1 >= 0 and grid[x - 1][y] == '1':
                        grid[x - 1][y] = '0'
                        q.append([x - 1, y])
                    if y - 1 >= 0 and grid[x][y - 1] == '1':
                        grid[x][y - 1] = '0'
                        q.append([x, y - 1])
                    if x + 1 < row and grid[x + 1][y] == '1':
                        grid[x + 1][y] = '0'
                        q.append([x + 1, y])
                    if y + 1 < col and grid[x][y + 1] == '1':
                        grid[x][y + 1] = '0'
                        q.append([x, y + 1])

    return res


grid = [["1", "1", "1"], ["0", "1", "0"], ["1", "1", "1"]]
print(numIsland(grid))
